//
//  Subset.swift
//  LeetCodeDemo
//
//  Created by Apple on 2020/12/21.
//

import Foundation

// MARK: 子集
class Subset {
    
    var res = [[Int]]()
    var temp = [Int]()
    
    func subsets(_ nums: [Int]) -> [[Int]] {
        dfs(0, nums)
        return res
    }
    
    func dfs(_ start: Int, _ nums: [Int]) {
        res.append(Array(temp))
        print(temp)
        for i in start..<nums.count {
            temp.append(nums[i])
            dfs(i + 1, nums)
            temp.removeLast()
        }
    }
    
    func test() {
        let res = subsets([1,2,3])
        print(res)
    }
    
}

class Subset01 {
    
    func subsets(_ nums: [Int]) -> [[Int]] {
        var res = [[Int]]()
        let n = nums.count
        let p = 1 << n
        for i in 0..<p {
            var temp = [Int]()
            for j in 0..<n {
                if (i >> j) & 1 == 1  {
                    temp.append(nums[j])
                }
            }
            res.append(temp)
        }
        return res
    }
    
    func test() {
        _ = subsets([1,2,3])
    }
}

class Subset02 {
    
    var res = [[Int]]()
    var temp = [Int]()
    
    func subsets(_ nums: [Int]) -> [[Int]] {
        backtrack(0, nums)
        return res
    }
    
    func backtrack(_ cur: Int, _ nums: [Int]) {
        if cur == nums.count {
            res.append(temp)
            print(temp)
            return
        }
        temp.append(nums[cur])
        backtrack(cur + 1, nums)
        temp.removeLast()
        backtrack(cur + 1, nums)
    }
    
    func test() {
        _ = subsets([1,2,3])
    }
    
}

